Addendum to: “Hamilton-laceable bi-powers of locally finite bipartite graphs” [Discrete Math. 345 (2022) 112777]

In this addendum we give a short and easy negative answer to the two questions raised in the original article.     

On Clique-Transversals and Clique-Independent Sets

A clique-transversal of a graph G is a subset of vertices intersecting all the cliques of G. A clique-independent set is a subset of pairwise disjoint cliques of G. Denote by _C (G) and _C (G) the cardinalities of the minimum clique-transversal and maximum clique-independent set of G, respectively. Say that G is clique-perfect when _C (H)= _C (H), for every induced subgraph H of G. In this paper, we prove that every graph not containing a 4-wheel nor a 3-fan as induced subgraphs and such that every odd cycle of length greater than 3 has a short chord is clique-perfect. The proof leads to polynomial time algorithms for finding the parameters _C (G) and _C (G), for graphs belonging to this class. In addition, we prove that to decide whether or not a given subset of vertices of a graph is a clique-transversal is Co-NP-Complete. The complexity of this problem has been mentioned as unknown in the literature. Finally, we describe a family of highly clique-imperfect graphs, that is, a family of graphs G whose difference _C (G)– _C (G) is arbitrarily large.     

The Flooding Time in Random Graphs

Based on our analysis of the hopcount of the shortest path between two arbitrary nodes in the class G _p (N) of random graphs, the corresponding flooding time is investigated. The flooding time T _N (p) is the minimum time needed to reach all other nodes from one node. We show that, after scaling, the flooding time T _N (p) converges in distribution to the two-fold convolution ^(2*) of the Gumbel distribution function (z)=exp (–e ^–z ), when the link density p _N satisfies Np _N /(log N)³ if N .     

Quantum Mayer Graphs for Coulomb Systems and the Analog of the Debye Potential

Within the Feynman–Kac path integral representation, the equilibrium quantities of a quantum plasma can be represented by Mayer graphs. The well known Coulomb divergencies that appear in these series are eliminated by partial resummations. In this paper, we propose a resummation scheme based on the introduction of a single effective potential that is the quantum analog of the Debye potential. A low density analysis of shows that it reduces, at short distances, to the bare Coulomb interaction between the charges (which is able to lead to bound states). At scale of the order of the Debye screening length ^–1 _D, approaches the classical Debye potential and, at large distances, it decays as a dipolar potential (this large distance behaviour is due to the quantum nature of the particles). The prototype graphs that result from the resummation obey the same diagrammatical rules as the classical graphs of the Abe–Meeron series. We give several applications that show the usefulness of to account for Coulombic effects at all distances in a coherent way.     

关于Menger定理的推广的注

本文给出了一个图为Ｍｅｎｇｅｒ型的一个充分必要条件，利用这个条件，我们拓广了已知的Ｍｅｎｇｅｒ型图的类。     

Optimal accumulation of Jacobian matrices by elimination methods on the dual computational graph

The accumulation of the Jacobian matrix F of a vector function can be regarded as a transformation of its linearized computational graph into a subgraph of the directed complete bipartite graph K_n,m. This transformation can be performed by applying different elimination techniques that may lead to varying costs for computing F. This paper introduces face elimination as the basic technique for accumulating Jacobian matrices by using a minimal number of arithmetic operations. Its superiority over both edge and vertex elimination methods is shown. The intention is to establish the conceptual basis for the ongoing development of algorithms for optimizing the computation of Jacobian matrices.     

A Solution to a Problem of Jacobson,Kézdy and Lehel

We solve a problem proposed by Jacobson, Kézdy, and Lehel [4] concerning the existence of forbidden induced subgraph characterizations of line graphs of linear k-uniform hypergraphs with sufficiently large minimal edge-degree. Actually, we prove that for each k3 there is a finite set Z(k) of graphs such that each graph G with minimum edge-degree at least 2k²–3k+1 is the line graph of a linear k-uniform hypergraph if and only if G is a Z(k)-free graph.Acknowledgments. We thank the anonymous referees, whose suggestions helped to improve the presentation of the paper.Winter 2002/2003 DIMACS Award is gratefully acknowledged2000 Mathematics Subject Classification: 05C65 (05C75, 05C85)     

Sparse <Emphasis Type="Italic">H</Emphasis>-Colourable Graphs of Bounded Maximum Degree

Let F be a graph of order at most k. We prove that for any integer g there is a graph G of girth at least g and of maximum degree at most 5k¹³ such that G admits a surjective homomorphism c to F, and moreover, for any F-pointed graph H with at most k vertices, and for any homomorphism h from G to H there is a unique homomorphism f from F to H such that h=fc. As a consequence, we prove that if H is a projective graph of order k, then for any finite family of prescribed mappings from a set X to V(H) (with ||=t), there is a graph G of arbitrary large girth and of maximum degree at most 5k^26mt (where m=|X|) such that and up to an automorphism of H, there are exactly t homomorphisms from G to H, each of which is an extension of an f.Supported in part by the National Science Council under grant NSC89-2115-M-110-012Final version received: June 9, 2003     

Cycles in 2-connected graphs

Let be a class of graphs on n vertices. For an integer c, let be the smallest integer such that if G is a graph in with more than edges, then G contains a cycle of length more than c. A classical result of Erdös and Gallai is that if is the class of all simple graphs on n vertices, then . The result is best possible when n-1 is divisible by c-1, in view of the graph consisting of copies of K_c all having exactly one vertex in common. Woodall improved the result by giving best possible bounds for the remaining cases when n-1 is not divisible by c-1, and conjectured that if is the class of all 2-connected simple graphs on n vertices, thenwhere , 2tc/2, is the number of edges in the graph obtained from K_c+1-t by adding n-(c+1-t) isolated vertices each joined to the same t vertices of K_c+1-t. By using a result of Woodall together with an edge-switching technique, we confirm Woodall's conjecture in this paper.